package mo.leetcode_top;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class L212 {

    private static final int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static int n = 0;
    private static int m = 0;

    public List<String> findWords(char[][] board, String[] words) {
        n = board.length;
        m = board[0].length;
        Map<Character, List<int[]>> mapper = new HashMap<>(n*m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char v = board[i][j];
                if (mapper.containsKey(v)) {
                    List<int[]> positions = mapper.get(v);
                    positions.add(new int[]{i, j});
                } else {
                    List<int[]> positions = new ArrayList<>();
                    positions.add(new int[]{i, j});
                    mapper.put(v, positions);
                }
            }
        }

        List<String> ans = new ArrayList<>();
        for (String word : words) {
            char first = word.charAt(0);
            if (!mapper.containsKey(first)) {
                continue;
            }
            for (int[] start : mapper.get(first)) {
                boolean[][] visited = new boolean[n][m];
                visited[start[0]][start[1]] = true;
                if (dfs(board, visited, word, 1, start[0], start[1])) {
                    ans.add(word);
                    break;
                }
            }
        }

        return ans;
    }

    private boolean dfs(char[][] board, boolean[][] visited, String word, int position, int x, int y) {
        if (word.length() == position) {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && board[nx][ny] == word.charAt(position)) {
                visited[nx][ny] = true;
                if (dfs(board, visited, word, position+1, nx, ny)) {
                    return true;
                }
                visited[nx][ny] = false;
            }
        }
        return false;
    }


    class Solution {
         class Trie {
            private final Map<Character, Trie> trieMap = new HashMap<>();
            private String word;
        }

        private final Trie root = new Trie();

        private char[][] board;

        private int len;
        private int height;

        private final List<String> result = new ArrayList<>();

        public List<String> findWords(char[][] board, String[] words) {
            init(board, words);
            for (int y = 0; y < board.length; y++) {
                for (int x = 0; x < board[y].length; x++) {
                    if (root.trieMap.containsKey(board[y][x])) {
                        backtracking(root, y, x);
                    }
                }
            }
            return result;
        }

        private void backtracking(Trie trie, int y, int x) {
            char temp = board[y][x];
            board[y][x] = '#';
            Trie curr = trie.trieMap.get(temp);
            if (curr.word != null) {
                result.add(curr.word);
                curr.word = null;
            }
            if (!curr.trieMap.isEmpty()) {
                int[] yOffset = new int[]{-1, 1, 0, 0},
                        xOffset = new int[]{0, 0, -1, 1};
                for (int i = 0; i < 4; i++) {
                    int newY = y + yOffset[i],
                            newX = x + xOffset[i];
                    if (newX < 0 || newY < 0 || newX >= len || newY >= height) continue;
                    if (curr.trieMap.containsKey(board[newY][newX])) backtracking(curr, newY, newX);
                }
            }
            if (curr.trieMap.isEmpty()) {
                trie.trieMap.remove(temp);
            }
            board[y][x] = temp;
        }

        private void insertionTrie(String word) {
            Trie trie = this.root;
            for (char value : new StringBuilder(word).reverse().toString().toCharArray()) {
                if (trie.trieMap.containsKey(value)) {
                    trie = trie.trieMap.get(value);
                } else {
                    Trie temp = new Trie();
                    trie.trieMap.put(value, temp);
                    trie = temp;
                }
            }
            trie.word = word;
        }

        private void init(char[][] board, String[] words) {
            this.board = board;
            len = board[0].length;
            height = board.length;
            for (String word : words) {
                insertionTrie(word);
            }
        }
    }

}
